using System;
using System.Text;
using System.Collections;
using System.Text.RegularExpressions;

namespace BigNumbers
{
    /// <summary>
    /// This class can be used to create and manage bigIntegers.
    /// A bigint can "only" have 4*Int32.MaxValue digits = 8589934588 digits
    /// </summary>
    public class BigInt
    {
        #region Declarations
        internal static readonly int BASENUMBER = 10000;
        internal static readonly int LENBASENUMBER = Convert.ToInt32(Math.Log10((double)BASENUMBER));
        private static BigInt m_i0 = new BigInt(0);
        private static BigInt m_i1 = new BigInt(1);
        private static BigInt m_im1 = new BigInt(-1);
        private static BigInt m_i2 = new BigInt(2);
        private static BigInt m_i3 = new BigInt(3);
        private static BigInt m_i5 = new BigInt(5);
        private static BigInt m_i10 = new BigInt(10);
        internal int[] m_aNumbers;
        internal int m_iTopArray;
        internal int m_iSign;		// -1 neg, 0 zero, 1 pos		
        #endregion Declarations

        #region Private Enum
        internal enum CompareType
        {
            Greater,
            Lesser,
            Equal
        }
        #endregion

        #region Constructors
        private BigInt()
        { }

        /// <summary>
        /// Create big int
        /// </summary>
        /// <param name="sNumber"> String param : only contains numbers or +-. If KO throw exception </param>
        public BigInt(string sNumber)
        {
            if (sNumber == null || sNumber == "")
                throw new ArgumentNullException("Can't create BigInt with null value");

            if (!new Regex(@"^\s*[+-]{0,1}\s*\d*\s*$").IsMatch(sNumber))
                throw new FormatException("Wrong format number");

            sNumber = sNumber.Trim().Replace(" ", string.Empty);
            int iLenInit = sNumber.Length;
            string sRes = string.Empty;
            switch (sNumber.Substring(0, 1))
            {
                case "+":
                    m_iSign = 1;
                    iLenInit--;
                    sRes = sNumber.Substring(1);
                    break;

                case "-":
                    m_iSign = -1;
                    sRes = sNumber.Substring(1);
                    iLenInit--;
                    break;

                case "0":
                case "1":
                case "2":
                case "3":
                case "4":
                case "5":
                case "6":
                case "7":
                case "8":
                case "9":
                    m_iSign = 1;
                    sRes = sNumber;
                    break;
            }

            int iLen = (int)(iLenInit / LENBASENUMBER);
            int n;
            m_aNumbers = new int[iLen + 1];
            m_iTopArray = iLen;

            for (int i = 0; i < iLen; i++)
            {
                n = Convert.ToInt32(sRes.Substring((int)(iLenInit - (i + 1) * LENBASENUMBER), (int)LENBASENUMBER));
                m_aNumbers[i] = n;
            }

            if (iLenInit - iLen * LENBASENUMBER != 0)
            {
                n = Convert.ToInt32(sRes.Substring(0, (int)(iLenInit - iLen * LENBASENUMBER)));
                m_aNumbers[iLen] = n;
            }
            Canonize();
        }

        /// <summary>
        /// Create big int starting from an long
        /// </summary>
        /// <param name="iNumber"> long param : </param>
        public BigInt(long iNumber)
        {
            m_aNumbers = new int[20 / LENBASENUMBER + 1];
            m_iTopArray = -1;
            m_iSign = Math.Sign(iNumber);
            do
            {
                m_aNumbers[m_iTopArray + 1] = (int)(Math.Abs(iNumber) % (long)BASENUMBER);
                iNumber = iNumber / BASENUMBER;
                m_iTopArray++;
            }
            while (iNumber != 0);
        }

        /// <summary>
        /// Creates the cells of the array
        /// </summary>
        /// <param name="iTop"> iTop = ArrayTop = len(nombre) -1 </param>
        internal static BigInt CreateBigInt(int iTop)
        {
            BigInt bi = new BigInt();
            bi.m_aNumbers = new int[iTop + 1];
            bi.m_iTopArray = iTop;
            bi.m_iSign = 1;

            return bi;
        }

        #endregion Constructors

        #region Properties
        /// <summary>
        /// Return the BigInt 0
        /// </summary>
        public static BigInt Zero
        {
            get
            {
                return m_i0;
            }
        }

        /// <summary>
        /// Return the BigInt 1
        /// </summary>
        public static BigInt One
        {
            get
            {
                return m_i1;
            }
        }

        /// <summary>
        /// Return the BigInt -1
        /// </summary>
        public static BigInt MinusOne
        {
            get
            {
                return m_im1;
            }
        }

        /// <summary>
        /// Return the BigInt 2
        /// </summary>
        public static BigInt Two
        {
            get
            {
                return m_i2;
            }
        }

        /// <summary>
        /// Return the BigInt 3
        /// </summary>
        public static BigInt Three
        {
            get
            {
                return m_i3;
            }
        }

        /// <summary>
        /// Return the BigInt 5
        /// </summary>
        public static BigInt Five
        {
            get
            {
                return m_i5;
            }
        }

        /// <summary>
        /// Return the BigInt 10
        /// </summary>
        public static BigInt Ten
        {
            get
            {
                return m_i10;
            }
        }

        /// <summary>
        /// Length
        /// </summary>
        /// <returns> int </returns>
        public int Length
        {
            get
            {
                return LENBASENUMBER * (m_iTopArray + 1);
            }
        }

        /// <summary>
        /// The sign of the big integer
        /// </summary>
        /// <returns> -1 if negative, 0 if null, 1 if positive</returns>
        public int Sign
        {
            get
            {
                return m_iSign;
            }
        }
        #endregion Properties

        #region Public Methods
        /// <summary>
        /// The sum of all the digits 
        /// </summary>
        /// <returns> The sum of all the digits </returns>
        public long DigitsSum()
        {
            long iSum = 0;
            for (int i = 0; i <= m_iTopArray; i++)
                iSum += m_aNumbers[i];

            return iSum;
        }

        /// <summary>
        /// To String
        /// </summary>
        /// <returns> a string representing the big int </returns>
        override public string ToString()
        {
            if (m_aNumbers == null) return ("!!! BigInteger is null");

            string sFormat = BASENUMBER.ToString().Substring(1);

            if (m_iSign == 0)
                return "0";

            StringBuilder s = new StringBuilder();
            s.Append(m_aNumbers[m_iTopArray].ToString());
            for (int i = 1; i <= m_iTopArray; i++)
                s.Append(m_aNumbers[m_iTopArray - i].ToString(sFormat));

            if (m_iSign == 1)
                return s.ToString();
            else // m_iSign = -1
                return "-" + s.ToString();
        }

        /// <summary>
        /// HashCode
        /// </summary>
        /// <returns>int</returns>		
        public override int GetHashCode()
        {
            return this.ToString().GetHashCode();
        }

        /// <summary>
        /// Equals
        /// </summary>
        /// <param name="o"></param>
        /// <returns> bool </returns>
        public override bool Equals(object o)
        {
            BigInt bi = (BigInt)o;
            return (this == bi);
        }

        /// <summary>
        /// Clone a BigInt
        /// </summary>
        /// <returns> bigint</returns>
        public BigInt Clone()
        {
            BigInt bi = CreateBigInt(m_iTopArray);
            bi.m_iTopArray = m_iTopArray;
            bi.m_aNumbers = m_aNumbers;
            bi.m_iSign = m_iSign;
            bi.Canonize();
            return bi;
        }
        #endregion Public Methods

        #region Overload unary operators
        /// <summary>
        /// Return the opposite of the number
        /// </summary>
        /// <param name="bi1"></param>
        /// <returns> BigInt </returns>
        public static BigInt operator -(BigInt bi1)
        {
            if (bi1.m_iSign == 0)
                return bi1.Clone();
            else
            {
                BigInt bi = CreateBigInt(bi1.m_iTopArray);
                bi.m_iTopArray = bi1.m_iTopArray;
                bi.m_aNumbers = bi1.m_aNumbers;
                bi.m_iSign = -bi1.m_iSign;
                return bi;
            }
        }

        /// <summary>
        /// Return the number
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> BigInt </returns>
        public static BigInt operator +(BigInt bi)
        {
            return bi.Clone();
        }

        /// <summary>
        /// Increment the number
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> BigInt </returns>
        public static BigInt operator ++(BigInt bi)
        {
            if (bi == MinusOne)
                return Zero;

            if (bi.m_iSign == 0)
                return One;

            return PlusMinusOne(bi, 1);
        }

        /// <summary>
        /// Decrement the number
        /// </summary>
        /// <param name="bi"></param>
        /// <returns> BigInt </returns>
        public static BigInt operator --(BigInt bi)
        {
            if (bi == One)
                return Zero;

            if (bi == Zero)
                return MinusOne;

            return PlusMinusOne(bi, -1);
        }
        #endregion

        #region Overload Binary operators
        /// <summary>
        /// Return i1 + i2
        /// </summary>
        /// <param name="i1"></param>
        /// <param name="i2"></param>
        /// <returns></returns>
        public static BigInt operator +(BigInt i1, BigInt i2)
        {
            BigInt bi = null;

            if (i1.m_iSign == 0) return i2.Clone();
            if (i2.m_iSign == 0) return i1.Clone();

            if (i1.m_iSign == i2.m_iSign)
            {
                bi = Add(i1, i2);
                bi.m_iSign = i1.m_iSign;
            }
            else
            {
                switch (Compare(i1, i2))
                {
                    case CompareType.Equal:
                        bi = BigInt.Zero;
                        break;

                    case CompareType.Greater:
                        bi = Sub(i1, i2);
                        bi.m_iSign = i1.m_iSign;
                        break;

                    case CompareType.Lesser:
                        bi = Sub(i2, i1);
                        bi.m_iSign = i2.m_iSign;
                        break;

                }
            }

            return bi;
        }

        /// <summary>
        /// Return i1 - i2
        /// </summary>
        /// <param name="i1"></param>
        /// <param name="i2"></param>
        /// <returns></returns>
        public static BigInt operator -(BigInt i1, BigInt i2)
        {
            return i1 + (-i2);
        }

        /// <summary>
        /// = bi1 * bi2
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> BigInt </returns>
        public static BigInt operator *(BigInt bi1, BigInt bi2)
        {
            if (bi1.m_iSign == 0) return BigInt.Zero;
            if (bi2.m_iSign == 0) return BigInt.Zero;
            int n1 = bi1.m_iTopArray;
            int n2 = bi2.m_iTopArray;

            // Create BigInt result
            BigInt biRes = CreateBigInt(n1 + n2 + 1);
            for (int i = 0; i <= n1 + n2 + 1; i++) biRes.m_aNumbers[i] = 0;
            int nCarry = 0;

            for (int i = 0; i <= n2; i++)
            {
                if (bi2.m_aNumbers[i] != 0)
                {
                    for (int j = 0; j <= n1; j++)
                    {
                        int res = biRes.m_aNumbers[i + j] + nCarry + bi2.m_aNumbers[i] * bi1.m_aNumbers[j];
                        biRes.m_aNumbers[i + j] = res % BASENUMBER;
                        nCarry = res / BASENUMBER;
                    }

                    if (nCarry != 0)
                    {
                        biRes.m_aNumbers[i + n1 + 1] = nCarry;
                        nCarry = 0;
                    }
                }
            }

            biRes.m_iSign = bi1.m_iSign * bi2.m_iSign;
            biRes.Canonize();
            return biRes;
        }

        /// <summary>
        /// = bi1 / bi2
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> BigInt </returns>
        public static BigInt operator /(BigInt bi1, BigInt bi2)
        {
            BigInt biMod = null;
            if (bi2 == Zero)
                throw new ArithmeticException("division by zero");

            if (bi2 == One)
                return bi1;

            if (bi1 == Zero)
                return Zero;

            BigInt bi3 = Calculus.Divide(Calculus.Abs(bi1), Calculus.Abs(bi2), ref biMod);
            if (bi1.m_iSign == bi2.m_iSign)
                bi3.m_iSign = 1;
            else
                bi3.m_iSign = -1;

            bi3.Canonize();
            return bi3;
        }

        /// <summary>
        /// = bi1 % bi2
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> BigInt </returns>
        public static BigInt operator %(BigInt bi1, BigInt bi2)
        {
            BigInt biMod = null;
            if (bi2 == Zero)
                throw new ArithmeticException("division by zero");

            if (bi2 == One)
                return Zero;

            if (bi1 == Zero)
                return bi2.Clone();

            Calculus.Divide(Calculus.Abs(bi1), Calculus.Abs(bi2), ref biMod);
            biMod.m_iSign = bi1.m_iSign;
            biMod.Canonize();
            return biMod;
        }

        /// <summary>
        /// Return true if bi1 > bi2
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> true or false </returns>
        public static bool operator >(BigInt bi1, BigInt bi2)
        {
            if (bi1.m_iSign > bi2.m_iSign)
                return true;

            if (bi1.m_iSign < bi2.m_iSign)
                return false;

            // equals signs
            switch (Compare(bi1, bi2))
            {
                case CompareType.Greater:
                    return (bi1.m_iSign != -1);

                case CompareType.Lesser:
                    return (bi1.m_iSign == -1);

                default:
                    return false;
            }
        }

        /// <summary>
        /// Return true if bi1 lesser than bi2
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> true or false </returns>
        public static bool operator <(BigInt bi1, BigInt bi2)
        {
            if (bi1.m_iSign > bi2.m_iSign)
                return false;

            if (bi1.m_iSign < bi2.m_iSign)
                return true;

            // equals signs
            switch (Compare(bi1, bi2))
            {
                case CompareType.Lesser:
                    return (bi1.m_iSign != -1);

                case CompareType.Greater:
                    return (bi1.m_iSign == -1);

                default:
                    return false;
            }
        }

        /// <summary>
        /// Return true if bi1 lesser or equal bi2
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> true or false </returns>
        public static bool operator <=(BigInt bi1, BigInt bi2)
        {
            return !(bi1 > bi2);
        }

        /// <summary>
        /// Return true if bi1 >= bi2
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> true or false </returns>
        public static bool operator >=(BigInt bi1, BigInt bi2)
        {
            return !(bi1 < bi2);
        }

        /// <summary>
        /// Return true if bi1 == bi2
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> true or false </returns>
        public static bool operator ==(BigInt bi1, BigInt bi2)
        {
            if (bi1.m_iSign != bi2.m_iSign)
                return false;
            else
            {
                if (Compare(bi1, bi2) != CompareType.Equal)
                    return false;
                else
                    return true;
            }
        }

        /// <summary>
        /// Return true if bi1 != bi2
        /// </summary>
        /// <param name="bi1"></param>
        /// <param name="bi2"></param>
        /// <returns> true or false </returns>
        public static bool operator !=(BigInt bi1, BigInt bi2)
        {
            return !(bi1 == bi2);
        }


        /// <summary>
        /// Shift bi to the left. Warning : slow method
        /// </summary>
        /// <param name="bi"> Integer to shift </param>
        /// <param name="iCount"> Number of shifts </param>
        /// <returns> bi / 2  </returns>
        public static BigInt operator <<(BigInt bi, int iCount)
        {
            if (iCount < 0)
                return Zero;

            return bi / Calculus.Pow(Two, iCount);
        }

        /// <summary>
        /// Shift bi to the right. Warning : slow method
        /// </summary>
        /// <param name="bi"> Integer to shift </param>
        /// <param name="iCount"> Number of shifts </param>
        /// <returns> Return bi * 2 </returns>
        public static BigInt operator >>(BigInt bi, int iCount)
        {
            if (iCount < 0)
                return Zero;

            return bi * Calculus.Pow(Two, iCount);
        }
        #endregion

        #region Cast
        /// <summary>
        /// Cast a long in BigInt
        /// </summary>
        /// <param name="i"> the integer to cast</param>
        /// <returns> BigInt </returns>
        public static implicit operator BigInt(long i)
        {
            return new BigInt(i);
        }

        /// <summary>
        /// Cast a double in BigInt
        /// </summary>
        /// <param name="d"> the double to cast</param>
        /// <returns> BigInt </returns>
        public static explicit operator BigInt(double d)
        {
            return new BigInt((int)d);
        }

        /// <summary>
        /// Cast a BigInt in int
        /// </summary>
        /// <param name="bi"> BigInt </param>
        /// <returns> int </returns>
        public static explicit operator long(BigInt bi)
        {
            if (bi > Int64.MaxValue)
                return 0;
            else
                return Convert.ToInt64(bi.ToString());
        }



        #endregion Cast

        #region Private methods
        // Shift the number by i2 
        internal static BigInt Shift(BigInt bi1, int i2)
        {
            BigInt bi = CreateBigInt(bi1.m_iTopArray + i2);
            bi.m_iSign = bi1.m_iSign;
            for (int i = 0; i <= bi.m_iTopArray; i++)
            {
                if (i < i2)
                    bi.m_aNumbers[i] = 0;
                else
                    bi.m_aNumbers[i] = bi1.m_aNumbers[i - i2];
            }
            return bi;
        }

        // Multiply bi1 
        internal static BigInt MultiplyBySmallInt(BigInt bi1, int i2)
        {
            if (i2 == 0)
                return BigInt.Zero;

            BigInt bi = CreateBigInt(bi1.m_iTopArray + 1);
            int nCarry = 0;
            for (int i = 0; i <= bi1.m_iTopArray; i++)
            {
                int nTemp = bi1.m_aNumbers[i] * i2 + nCarry;
                bi.m_aNumbers[i] = nTemp % BASENUMBER;
                nCarry = nTemp / BASENUMBER;
            }
            if (nCarry != 0)
                bi.m_aNumbers[bi1.m_iTopArray + 1] = nCarry;
            else
                bi.m_iTopArray--;

            return bi;
        }

        // find how much you find bi2 into bi1 where the result is an int, bi1 & bi2 positive
        internal static int DivideBy(BigInt bi1, BigInt bi2)
        {

            if (bi1 < bi2)
                return 0;
            if (bi1 == bi2)
                return 1;

            int i1 = 0;
            int i2 = BASENUMBER;
            int i = (i1 + i2) / 2;
            BigInt biRes = MultiplyBySmallInt(bi2, i);

            do
            {

                if (biRes > bi1)
                    i2 = i;
                else
                    i1 = i;

                i = (i1 + i2) / 2;
                biRes = MultiplyBySmallInt(bi2, i);
            } while (biRes > bi1 || bi1 - biRes >= bi2);

            return i;
        }

        // Compare absolute values
        internal static CompareType Compare(BigInt bi1, BigInt bi2)
        {
            int n1 = bi1.m_iTopArray;
            int n2 = bi2.m_iTopArray;
            if (n1 > n2)
                return CompareType.Greater;
            if (n1 < n2)
                return CompareType.Lesser;

            int i = n1;
            while (i != -1 && bi1.m_aNumbers[i] == bi2.m_aNumbers[i]) i--;
            if (i == -1)
            {
                if (bi1.m_aNumbers[0] > bi2.m_aNumbers[0])
                    return CompareType.Greater;
                if (bi1.m_aNumbers[0] < bi2.m_aNumbers[0])
                    return CompareType.Lesser;

                return CompareType.Equal;
            }
            else
            {
                if (bi1.m_aNumbers[i] > bi2.m_aNumbers[i])
                    return CompareType.Greater;
                else
                    return CompareType.Lesser;
            }
        }

        // return bi1 + bi2 Doesn't care about the sign
        private static BigInt Add(BigInt bi1, BigInt bi2)
        {
            int n1 = bi1.m_iTopArray;
            int n2 = bi2.m_iTopArray;
            int nMaxSize = Math.Max(n1, n2);
            int nMinSize = Math.Min(n1, n2);
            BigInt biRes = CreateBigInt(nMaxSize + 1);
            biRes.m_iTopArray = nMaxSize;
            int nCarry = 0;
            int nRes;

            for (int i = 0; i <= nMaxSize; i++)
            {
                if (i <= nMinSize)
                {
                    nRes = (bi1.m_aNumbers[i] + bi2.m_aNumbers[i] + nCarry) % BASENUMBER;
                    nCarry = (bi1.m_aNumbers[i] + bi2.m_aNumbers[i] + nCarry) / BASENUMBER;
                }
                else
                {
                    if (i > n1)
                    {
                        nRes = (bi2.m_aNumbers[i] + nCarry) % BASENUMBER;
                        nCarry = (bi2.m_aNumbers[i] + nCarry) / BASENUMBER;
                    }
                    else
                    {
                        nRes = (bi1.m_aNumbers[i] + nCarry) % BASENUMBER;
                        nCarry = (bi1.m_aNumbers[i] + nCarry) / BASENUMBER;
                    }
                }
                biRes.m_aNumbers[i] = nRes;
            }

            if (nCarry != 0) biRes.m_aNumbers[++biRes.m_iTopArray] = nCarry;

            biRes.Canonize();
            return biRes;
        }

        // i1 > i2. Doesn't care about the sign
        private static BigInt Sub(BigInt bi1, BigInt bi2)
        {
            int n1 = bi1.m_iTopArray;
            int n2 = bi2.m_iTopArray;
            int nMaxSize = Math.Max(n1, n2);
            int nMinSize = Math.Min(n1, n2);
            BigInt biRes = CreateBigInt(nMaxSize);
            int nCarry = 0;
            int nRes;

            for (int i = 0; i <= nMaxSize; i++)
            {
                int i1 = bi1.m_aNumbers[i];
                if (i <= nMinSize)
                {
                    int i2 = bi2.m_aNumbers[i];
                    if (i1 >= i2 + nCarry)
                    {
                        nRes = i1 - nCarry - i2;
                        nCarry = 0;
                    }
                    else
                    {
                        nRes = i1 - nCarry - i2 + BASENUMBER;
                        nCarry = 1;
                    }
                }
                else
                {
                    if (i1 >= nCarry)
                    {
                        nRes = i1 - nCarry;
                        nCarry = 0;
                    }
                    else
                    {
                        nRes = i1 - nCarry + BASENUMBER;
                        nCarry = 1;
                    }
                }
                biRes.m_aNumbers[i] = nRes;
            }

            biRes.Canonize();
            return biRes;
        }

        // Remove all beginning zeros
        internal void Canonize()
        {
            int i = m_iTopArray;

            while (i != 0 && m_aNumbers[i] == 0)
            {
                m_iTopArray--;
                i--;
            }

            // Transform -0 in 0
            if (m_iTopArray == 0 && m_aNumbers[0] == 0) m_iSign = 0;
        }

        // add or substract 1 to bi. bi must be different of 0, -1 if Plus & 1 if Minus
        private static BigInt PlusMinusOne(BigInt bi, int iSign)
        {
            int nCarry = iSign * bi.m_iSign;
            BigInt biRes = CreateBigInt(bi.m_iTopArray + 1);
            biRes.m_iSign = bi.m_iSign;
            for (int i = 0; i <= bi.m_iTopArray; i++)
            {
                if (nCarry == -1 && bi.m_aNumbers[i] == 0)
                {
                    biRes.m_aNumbers[i] = BASENUMBER - 1;
                    nCarry = -1;
                }
                else
                {
                    biRes.m_aNumbers[i] = (bi.m_aNumbers[i] + nCarry) % BASENUMBER;
                    nCarry = (bi.m_aNumbers[i] + nCarry) / BASENUMBER;
                }
            }
            if (nCarry != 0)
                biRes.m_aNumbers[biRes.m_iTopArray] = nCarry;
            else
                biRes.m_iTopArray--;

            biRes.Canonize();

            return biRes;
        }
        #endregion

    }
}
